import java.util.Arrays;

public class Solution2 {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        /*为什么要将数组大小设为 amount + 1 ？
        * 我觉得是考虑到 0 位置
        * 但是题上是这么说的：
        * ”为啥 dp 数组中的值都初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），
        * 所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。
        * 为啥不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢？
        * 因为后面有 dp[i - coin] + 1，这就会导致整型溢出。“*/
        memo = new int[amount + 1];
        Arrays.fill(memo,-666);
        return dp(coins,amount);
    }
    int dp(int[] coins, int amount){
        /*使用备忘录数组后，base case 出现了新的条件*/
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (memo[amount] != -666){
            return memo[amount];
        }
        /*接下来的判定照旧*/
        int res = Integer.MAX_VALUE;
        for(int coin : coins){
            int subProblem = dp(coins, amount - coin);
            if (subProblem == -1) continue;
            res = Math.min(res,subProblem + 1);
        }
        /*将计算结果存入备忘录*/
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}
